package com.lun.swordtowardoffer2.c04;

import com.lun.util.SinglyLinkedList.ListNode;

public class InsertNode {

	//注意head是指循环链表的某一点，不确保是最小值点或最大值点
	public void insert(ListNode head, int val) {
		ListNode newNode = new ListNode(val);
		if(head == null) {//循环链表为空
			head = newNode;
			head.next = head;
		}else if(head.next == head) {//循环链表内有1个节点
			head.next = newNode;
			newNode.next = head;
		}else {//循环链表内有2个节点及其以上
			ListNode max = head, curr =  head, next = head.next;
			
			//找到环合适的位置
			while(!(next == head || (curr.val <= newNode.val && newNode.val <= next.val))) {//找到环合适的位置
				curr = next;
				next = curr.next;
				if(curr.val > max.val)
					max = curr;
			}
			
			if(curr.val <= newNode.val && newNode.val <= next.val) {
				curr.next = newNode;
				newNode.next = next;
			}else {//最大值与最小值之间
				newNode.next = max.next;
				max.next = newNode;
			}
		}
	}
}
